/**********************************************************

@description:post thread tree
*File Name:postThreadTree.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Sat 26 Apr 2025 10:47:28 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct tnode{
	char data;
	struct tnode* lchild;
	struct tnode* rchild;
	struct tnode* parent;
	unsigned char ltag:1;//0->lchild, 1->pre 
	unsigned char rtag:1;//0->rchild, 1->next
}tnode;
void createTree1(tnode **n,char*data,int* idx,tnode* parent){
	char ch;
	ch=data[*idx];
	*idx+=1;
	if(ch == '#'){
		*n=NULL;		
	}else{
		*n=(tnode*)malloc(sizeof(tnode));
		(*n)->data=ch;
		(*n)->ltag=0;
		(*n)->rtag=0;
		(*n)->parent=parent;
		createTree1(&(*n)->lchild,data,idx,*n);
		createTree1(&(*n)->rchild,data,idx,*n);
	}
}
void postThread(tnode *t,tnode **pre){
	if(t){
		postThread(t->lchild,pre);
		postThread(t->rchild,pre);
		//dosomething
		if(!t->lchild){
			t->ltag=1;
			t->lchild=*pre;
		}
		if(*pre && !(*pre)->rchild){
			(*pre)->rtag=1;
			(*pre)->rchild=t;
		}
		*pre=t;
	}
}
typedef void (*visit)(tnode*);
void pn(tnode* n){
	if(n)
		printf("%c ",n->data);
}
tnode* getFirst(tnode *t){
	if(!t)
		return NULL;
	while(!t->ltag)
		t=t->lchild;
	if(!t->rtag){
		return getFirst(t->rchild);
	}
	return t;
}
tnode * getNext(tnode* node){
	tnode *ret=NULL;
	tnode *parent=node->parent;
	if(!parent)
		ret=NULL;
	else if(node->rtag)
		ret=node->rchild;
	else if(node==parent->lchild && !parent->rtag)
		ret=getFirst(parent->rchild);
	else if(node==parent->lchild && parent->rtag)
		ret=parent;
	else if(node==parent->rchild)
		ret=parent;
	return ret;
}
void postThreadTraverse(tnode* t,visit v){
	tnode* cur=getFirst(t);
	while(cur){
		v(cur);
		cur=getNext(cur);
	}
}

int main(int argc,char **argv){
	tnode* t=NULL;
	tnode* pre=NULL;
	int index=0;
	createTree1(&t,argv[1],&index,NULL);
	postThread(t,&pre);
	postThreadTraverse(t,pn);
	printf("\n");
	return 0;
}
